{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "aVqb4qlbXjI-"
   },
   "source": [
    "##### Copyright 2020 The OpenFermion Developers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "id": "Dk8ubIqnXl2B"
   },
   "outputs": [],
   "source": [
    "#@title Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "# https://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "kybNYuM7YeyH"
   },
   "source": [
    "# Lowering qubit requirements using binary codes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "cuXwrTlaXtYo"
   },
   "source": [
    "<table class=\"tfo-notebook-buttons\" align=\"left\">\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://quantumai.google/openfermion/tutorials/binary_code_transforms\"><img src=\"https://quantumai.google/site-assets/images/buttons/quantumai_logo_1x.png\" />View on QuantumAI</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/quantumlib/OpenFermion/blob/master/docs/tutorials/binary_code_transforms.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/colab_logo_1x.png\" />Run in Google Colab</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://github.com/quantumlib/OpenFermion/blob/master/docs/tutorials/binary_code_transforms.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/github_logo_1x.png\" />View source on GitHub</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a href=\"https://storage.googleapis.com/tensorflow_docs/OpenFermion/docs/tutorials/binary_code_transforms.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/download_icon_1x.png\" />Download notebook</a>\n",
    "  </td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "TtLEYcV8Yp1t"
   },
   "source": [
    "## Setup\n",
    "\n",
    "Install the OpenFermion package:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "5cbe6b680387"
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    import openfermion\n",
    "except ImportError:\n",
    "    !pip install git+https://github.com/quantumlib/OpenFermion.git@master#egg=openfermion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "4cc6d04dc630"
   },
   "source": [
    "## Introduction\n",
    "\n",
    "Molecular Hamiltonians are known to have certain symmetries that are not taken into account by mappings like the Jordan-Wigner or Bravyi-Kitaev transform. The most notable of such symmetries is the conservation of the total number of particles in the system. Since those symmetries effectively reduce the degrees of freedom of the system, one is able to reduce the number of qubits required for simulation by utilizing binary codes (arXiv:1712.07067). \n",
    "\n",
    "We can represent the symmetry-reduced Fermion basis by binary vectors of a set $\\mathcal{V} \\ni \\boldsymbol{\\nu}$, with $ \\boldsymbol{\\nu} = (\\nu_0, \\, \\nu_1, \\dots, \\, \\nu_{N-1} ) $, where every component $\\nu_i \\in \\lbrace 0, 1 \\rbrace $ and $N$ is the total number of Fermion modes.  These binary vectors $ \\boldsymbol{\\nu}$ are related to the actual basis states by: $$\n",
    "\\left[\\prod_{i=0}^{N-1} (a_i^{\\dagger})^{\\nu_i}  \\right] \\left|{\\text{vac}}\\right\\rangle \\, ,\n",
    "$$ where $ (a_i^\\dagger)^{0}=1$. The qubit basis, on the other hand, can be characterized by length-$n$ binary vectors $\\boldsymbol{\\omega}=(\\omega_0, \\, \\dots , \\, \\omega_{n-1})$, that represent an $n$-qubit basis state by:\n",
    "$$ \\left|{\\omega_0}\\right\\rangle  \\otimes \\left|\\omega_1\\right\\rangle \\otimes \\dots \\otimes  \\left|{\\omega_{n-1}}\\right\\rangle \\, .  $$ \n",
    "Since $\\mathcal{V}$ is a mere subset of the $N$-fold binary space, but the set of the vectors $\\boldsymbol{\\omega}$ spans the entire $n$-fold binary space we can assign every vector $\\boldsymbol{\\nu}$ to a vector $ \\boldsymbol{\\omega}$, such that $n<N$. This reduces the amount of qubits required by $(N-n)$. The mapping can be done by a binary code, a classical object that consists of an encoder function $\\boldsymbol{e}$ and a decoder function $\\boldsymbol{d}$. \n",
    "These functions relate the binary vectors $\\boldsymbol{e}(\\boldsymbol{\\nu})=\\boldsymbol{\\omega}$, $\\boldsymbol{d}(\\boldsymbol{\\omega})=\\boldsymbol{\\nu}$, such that $\\boldsymbol{d}(\\boldsymbol{e}(\\boldsymbol{\\nu}))=\\boldsymbol{\\nu}$.\n",
    "In OpenFermion, we, at the moment, allow for non-linear decoders $\\boldsymbol{d}$ and linear encoders $\\boldsymbol{e}(\\boldsymbol{\\nu})=A \\boldsymbol{\\nu}$, where the matrix multiplication with the $(n\\times N)$-binary matrix $A$ is $(\\text{mod 2})$ in every component. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "KluWcXkeo3-x"
   },
   "source": [
    "## Symbolic binary functions\n",
    "\n",
    "The non-linear binary functions for the components of the decoder are here modeled by the $\\text{BinaryPolynomial}$ class in openfermion.ops.\n",
    "For initialization we can conveniently use strings ('w0 w1 + w1 +1' for the binary function $\\boldsymbol{\\omega} \\to \\omega_0 \\omega_1 + \\omega_1 + 1 \\;\\text{mod 2}$), the native data structure or symbolic addition and multiplication."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "a7e6ea814bc4"
   },
   "outputs": [],
   "source": [
    "from openfermion.ops import BinaryPolynomial\n",
    "\n",
    "binary_1 = BinaryPolynomial('w0 w1 + w1 + 1')\n",
    "\n",
    "print(\"These three expressions are equivalent: \\n\", binary_1)\n",
    "print(BinaryPolynomial('w0') * BinaryPolynomial('w1 + 1') + BinaryPolynomial('1'))\n",
    "print(BinaryPolynomial([(1, 0), (1, ), ('one', )]))\n",
    "\n",
    "print('The native data type structure can be seen here:')\n",
    "print(binary_1.terms)\n",
    "print('We can always evaluate the expression for instance by the vector (w0, w1, w2) = (1, 0, 0):',\n",
    "      binary_1.evaluate('100'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "32fb8462ca63"
   },
   "source": [
    "## Binary codes\n",
    "\n",
    "The $\\text{BinaryCode}$ class bundles a decoder - a list of decoder components, which are instances of $\\text{BinaryPolynomial}$ - and an encoder - the matrix $A$ as sparse numpy array -  as a binary code. The constructor however admits (dense) numpy arrays, nested lists or tuples as input for $A$, and arrays, lists or tuples of $\\text{BinaryPolynomial}$ objects - or valid inputs for $\\text{BinaryPolynomial}$ constructors - as input for $\\boldsymbol{d}$. An instance of the $\\text{BinaryCode}$ class knows about the number of qubits and the number of modes in the mapping.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ffb859fb2ad3"
   },
   "outputs": [],
   "source": [
    "from openfermion.ops import BinaryCode\n",
    "\n",
    "code_1 = BinaryCode([[1, 0, 0], [0, 1, 0]], ['w0', 'w1', 'w0 + w1 + 1' ])\n",
    "\n",
    "print(code_1)\n",
    "print('number of qubits: ', code_1.n_qubits, '  number of Fermion modes: ', code_1.n_modes )\n",
    "print('encoding matrix: \\n', code_1.encoder.toarray())\n",
    "print('decoder: ', code_1.decoder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "03e9717ebd49"
   },
   "source": [
    "The code used in the example above, is in fact the (odd) Checksum code, and is implemented already - along with a few other examples from arxiv:1712.07067. In addition to the $\\text{checksum_code}$ the functions $\\text{weight_one_segment_code}$, $\\text{weight_two_segment_code}$, that output a subcode each, as well as $\\text{weight_one_binary_addressing_code}$ can be found under openfermion.transforms._code_transform_functions.\n",
    "\n",
    "There are two other ways to construct new codes from the ones given - both of them can be done conveniently with symbolic operations between two code objects $(\\boldsymbol{e}, \\boldsymbol{d})$ and $(\\boldsymbol{e^\\prime}, \\boldsymbol{d^\\prime})$ to yield a new code $(\\boldsymbol{e^{\\prime\\prime}}, \\boldsymbol{d^{\\prime\\prime}})$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ssoFxJ1fpTbu"
   },
   "source": [
    "### Appendage\n",
    "\n",
    "Input and output vectors of two codes are appended to each other such that:\n",
    "$$ e^{\\prime\\prime}(\\boldsymbol{\\nu} \\oplus \\boldsymbol{\\nu^{\\prime} })=\\boldsymbol{e}(\\boldsymbol{\\nu}) \\oplus \\boldsymbol{e^\\prime}(\\boldsymbol{\\nu^\\prime})\\, ,  \\qquad d^{\\prime\\prime}(\\boldsymbol{\\omega} \\oplus \\boldsymbol{\\omega^{\\prime} })=\\boldsymbol{d}(\\boldsymbol{\\omega}) \\oplus \\boldsymbol{d^\\prime}(\\boldsymbol{\\omega^\\prime}) \\, . $$\n",
    "This is implemented with symbolic addition of two $\\text{BinaryCode}$ objects (using + or += ) or, for appending several instances of the same code at once, multiplication of the $\\text{BinaryCode}$ with an integer. Appending codes is useful when we want to obtain a segment code, or a segmented transform."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-9bow2b7pSiH"
   },
   "source": [
    "### Concatenation\n",
    "\n",
    "Two codes can (if the corresponding vectors match in size) be applied consecutively, in the sense that the output of the encoder of the first code is input to the encoder of the second code. This defines an entirely new encoder, and the corresponding decoder is defined to undo this operation. \n",
    "$$ \\boldsymbol{e^{\\prime\\prime}}(\\boldsymbol{\\nu^{\\prime\\prime}})=\\boldsymbol{e^\\prime}\\left(\\boldsymbol{e}(\\boldsymbol{\\nu^{\\prime\\prime}}) \\right) \\, , \\qquad \\boldsymbol{d^{\\prime\\prime}}(\\boldsymbol{\\omega^{\\prime\\prime}})=\\boldsymbol{d}\\left(\\boldsymbol{d^\\prime}(\\boldsymbol{\\omega^{\\prime\\prime}}) \\right)\n",
    "$$\n",
    "This is done by symbolic multiplication of two $\\text{BinaryCode}$ instances (with \\* or \\*=  ). One can concatenate the codes with each other such that additional qubits can be saved (e.g. checksum code \\* segment code ), or to modify the resulting gates after transform (e.g. checksum code \\* Bravyi-Kitaev code).  \n",
    "\n",
    "A broad palette of codes is provided to help construct codes symbolically. \n",
    "The $\\text{jordan_wigner_code}$ can be appended to every code to fill the number of modes, concatenating the $\\text{bravyi_kitaev_code}$ or $\\text{parity_code}$ will modify the appearance of gates after the transform. The $\\text{interleaved_code}$ is useful to concatenate appended codes with if in Hamiltonians, Fermion operators are ordered by spin indexing even-odd (up-down-up-down-up ...) . This particular instance is used in the demonstration below.   \n",
    "\n",
    "Before we turn to describe the transformation, a word of warning has to be spoken here. Controlled gates that occur in the Hamiltonian by using non-linear codes are decomposed into Pauli strings, e.g. $\\text{CPHASE}(1,2)=\\frac{1}{2}(1+Z_1+Z_2-Z_1Z_2)$. In that way the amount of terms in a Hamiltonian might rise exponentially, if one chooses to use strongly non-linear codes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6gC5dHjupFCG"
   },
   "source": [
    "## Operator transform\n",
    "\n",
    "The actual transform of Fermion operators into qubit operators is done with the routine $\\text{binary_code_transform}$, that takes a Hamiltonian and a suitable code as inputs, outputting a qubit Hamiltonian.   \n",
    "Let us consider the case of a molecule with 4 modes where, due to the absence of magnetic interactions, the set of valid modes is only $$ \\mathcal{V}=\\lbrace (1,\\, 1,\\, 0,\\, 0 ),\\,(1,\\, 0,\\, 0,\\, 1 ),\\,(0,\\, 1,\\, 1,\\, 0 ),\\,(0,\\, 0,\\, 1,\\, 1 )\\rbrace \\, .$$\n",
    "One can either use an (even weight) checksum code to save a single qubit, or use and (odd weight) checksum code on spin-up and -down modes each to save two qubits. Since the ordering is even-odd, however, this requires to concatenate the with the interleaved code, which switches the spin indexing of the qubits from even-odd ordering to up-then-down. Instead of using the interleaved code, we can also use the reorder function to apply up-then-down ordering on the hamiltonian."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "9d067c39aaa9"
   },
   "outputs": [],
   "source": [
    "from openfermion.transforms import *\n",
    "from openfermion.chem import MolecularData\n",
    "from openfermion.transforms import binary_code_transform\n",
    "from openfermion.transforms import get_fermion_operator\n",
    "from openfermion.linalg import eigenspectrum\n",
    "from openfermion.transforms import normal_ordered, reorder\n",
    "from openfermion.utils import up_then_down\n",
    "\n",
    "def LiH_hamiltonian():\n",
    "    geometry = [('Li', (0., 0., 0.)), ('H', (0., 0., 1.45))]\n",
    "    molecule = MolecularData(geometry, 'sto-3g', 1,\n",
    "                             description=\"1.45\")\n",
    "    molecule.load()\n",
    "    molecular_hamiltonian = molecule.get_molecular_hamiltonian(occupied_indices = [0], active_indices = [1,2])\n",
    "    hamiltonian = normal_ordered(get_fermion_operator(molecular_hamiltonian))\n",
    "    return hamiltonian\n",
    "\n",
    "hamiltonian = LiH_hamiltonian()\n",
    "print('Fermionic Hamiltonian')\n",
    "print (hamiltonian)\n",
    "print(\"The eigenspectrum\")\n",
    "print(eigenspectrum(hamiltonian))\n",
    "\n",
    "print('\\n-----\\n')\n",
    "jw = binary_code_transform(hamiltonian, jordan_wigner_code(4))\n",
    "print('Jordan-Wigner transformed Hamiltonian')\n",
    "print(jw)\n",
    "print(\"the eigenspectrum of the transformed hamiltonian\")\n",
    "print(eigenspectrum(jw))\n",
    "\n",
    "print('\\n-----\\n')\n",
    "cksm_save_one = binary_code_transform(hamiltonian, checksum_code(4,0))\n",
    "print('Even-weight checksum code')\n",
    "print(cksm_save_one)\n",
    "print(\"the eigenspectrum of the transformed hamiltonian\")\n",
    "print(eigenspectrum(cksm_save_one))\n",
    "\n",
    "print('\\n-----\\n')\n",
    "up_down_save_two = binary_code_transform(hamiltonian, interleaved_code(4)*(2*checksum_code(2,1)))\n",
    "print('Double odd-weight checksum codes')\n",
    "print(up_down_save_two )\n",
    "print(\"the eigenspectrum of the transformed hamiltonian\")\n",
    "print(eigenspectrum(up_down_save_two ))\n",
    "\n",
    "print('\\n-----\\n')\n",
    "print('Instead of interleaving, we can apply up-then-down ordering using the reorder function:')\n",
    "up_down_save_two = binary_code_transform(reorder(hamiltonian,up_then_down), 2*checksum_code(2,1))\n",
    "print(up_down_save_two)\n",
    "print(\"the eigenspectrum of the transformed hamiltonian\")\n",
    "print(eigenspectrum(up_down_save_two))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "binary_code_transforms.ipynb",
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
